1. Field of the Invention
This invention relates to an error correction coding/decoding method and circuit, and more specifically, to a method of coding/decoding Reed-Solomon codes formed of symbols larger than information symbols when data is transmitted such as in data transfer and data recording, and a circuit for implementing this method.
2. Description of Related Art
Error correction coding is often used when digital information is transmitted. xe2x80x9cCode Theoremxe2x80x9d edited by the Institute of Electronic Information Communication (Denshi Joho Tsushin Gakkairon), written by Hideo Imai, first edition published on Mar. 15, 1990, various error correction coding and decoding techniques are disclosed. One of these is Reed-Solomon coding, a method which performs symbol error correction on a symbol of 8 bits, which has high compatibility with computers or digital instruments, and which is therefore widely used for information transfer or recording.
Flash memories, which in addition to permitting write erase can store data even without power and achieve higher levels of integration than DRAM, are now attracting interest, and it is hoped to use them as memory devices. However flash memories suffer from the disadvantage that when a large number of writes and erasures are performed, internal cells are damaged and data can be destroyed. Error correction is therefore often used when data is recorded on flash memories. Further when data is erased, all data becomes xe2x80x9c1xe2x80x9d, so this is used to verify the erasure.
In general, when data is recorded on a disk memory, 512 bytes of information data are stored as one sector. Also as memories store data in units of 8 bits, a Reed-Solomon code is used whereof 8 bits comprise one symbol. However in such a Reed-Solomon code wherein 8 bits comprise one symbol, the coding length is generally limited to 255, and consequently the data has to be split into a plurality of code words.
Alternatively, for example, data may be protected by a Reed-Solomon code wherein one symbol is 10 bits. In this case it is generally possible to have a coding length of up to 1023 symbols, so 1 sector of data is one code word.
FIG. 15 shows a typical code structure of a conventional error correction coding and decoding method, and in particular a (418, 410) Reed-Solomon code.
Herein, xe2x80x9c418xe2x80x9d is the code symbol length and xe2x80x9c410xe2x80x9d is the information length. Four symbols can be corrected. In FIGS. 15, 30 is a compressed part, 31 is a real information data symbol part, 32 is a check symbol part and 36 is a dummy symbol part.
The Reed-Solomon code shown in FIG. 15 actually has a length of 1023 symbols, but it is coded assuming that the 605 symbols of the compressed part 30 are 0. Further if 1 sector is 512 bytes, there will be 4096 bits, i.e. 4 bits short of the number necessary to assign 10 bits/symbol. The 4 bit dummy symbol 36 is therefore added, and with a real information data symbol part 31 of 410 symbols, 8 symbols of 10 bits are generated for the check symbol part 32.
Next, a coding circuit for generating check bytes in the Reed-Solomon code of FIG. 15 will be described with reference to FIG. 16. Herein, data input and output of check symbols are handled in 8 bit units so that these operations can be normally performed by a flash memory. In FIGS. 16, 22 is an 8 bit information data input terminal, 19 is a 8 bit/10 bit conversion circuit, 23 is a coding circuit for Reed-Solomon codes on a GF (2E10), 26 is a 8 bit check symbol output terminal, and 29 is a 10 bit/8 bit conversion circuit.
The operation of the structure in FIG. 16 will be described. Check symbols of the Reed-Solomon code are first generated in the coding circuit 23, for which purpose the circuit 23 is first cleared to xe2x80x9c0xe2x80x9d.
First, 8 bit information data is input from an information data input terminal 22, and then input to the 8 bit/10 bit conversion circuit 19. When 10 bit information has accumulated in the 8 bit/10 bit conversion circuit 19, this information is input to the coding circuit 23.
When the entire real information data symbol part 31 is input to the coding circuit 23 including the 4 bits of the dummy symbol part 36 in FIG. 15, the 8 symbol (80 bit) check symbol part 32 is obtained. This means there is no need to calculate the compressed code part 30.
The check symbol part 32 is subjected to a 10 bit/8 bit conversion by a 10 bit/8 bit conversion circuit from the top down, and check byte data is output from the check symbol output terminal 26 every 8 bits. In other words, 10 byte data is output as check symbols.
Next, a conventional decoding method and in particular a syndrome calculation will be described with reference to FIG. 17. The construction of FIG. 17 assumes a flash memory having also a data erasure check function. In FIG. 17, 1 is a data input terminal for inputting 8 bit received data, 5 is a Galois field summing circuit on a GF (2E10), 7 is a 10 bit register, 8 is a Galois field coefficient multiplying circuit on a GF (2E10), 9 is a syndrome output terminal, 20 is a FF check circuit for checking whether or not all 8 bit data is xe2x80x9c1xe2x80x9d, i.e. whether or not it is xe2x80x9cFFxe2x80x9d in terms of HEX code, and 21 is an erasure check flag output terminal.
First, error correction decoding is performed, it being assumed that the register 7 is first cleared to 0. Received data input from the data input terminal 1 is input to the 8 bit/10 bit conversion circuit 19. When 10 bit data has accumulated in the 8 bit/10 bit conversion circuit 19, a Galois field summation is performed on this information and the output of the Galois field coefficient multiplying circuit 8 in the Galois field summing circuit 5. The summation result is input to the register 7. The output of the register 7 is transmitted to the input terminal of the Galois field coefficient multiplying circuit 8.
The state of the register 7 when all of the real information data symbol part 31 and check symbol part 32 has been input, is the syndrome Sj, and this is output from the syndrome output terminal 9.
At that time, even if a slip of symbol units should occur when the leading data symbol of the Reed-Solomon code is xe2x80x9c0xe2x80x9d, there is still a possibility that error correction decoding will take place with the slip still present as Reed-Solomon codes are cyclic codes.
On the other hand when data is erased in a flash memory, all data becomes xe2x80x9c1xe2x80x9d, but it is necessary to verify whether or not the erasure has been performed without any errors.
In this case, 8 bit data is input to the FF check circuit 20 from the data input terminal 1, and if xe2x80x9c0xe2x80x9d is detected in even one bit, an error flag is output by the erasure check flag output terminal 21.
Now conventionally, when error correction is performed, decoding of codes formed from product codes is performed after first storing them in a memory. FIG. 18 is a block diagram of a circuit showing an example of such a case. In the figure, 59 is a buffer memory, 60 is a syndrome circuit, 63 is an error position/magnitude detecting circuit which determines error position and magnitude, 64 is a correction circuit, and 65 is a post-correction decoded data output terminal.
In the above construction, coded data input from the data input terminal 1 is stored in the buffer memory 59. Subsequently interleaving is released, the data is converted to a coded sequence and input to the syndrome circuit 60. Based on the syndrome thereby obtained, error positions and magnitudes are determined by the error position/magnitude detecting circuit 63, error position data in the buffer memory 59 is read by the correction circuit 64, the errors are corrected, and the data is written to the buffer memory 59. In the case of product codes, this decoding operation is repeated a plurality of times, and all data is decoded and output by the decoded data output terminal 65.
When the aforesaid operations are performed by one buffer memory, input of received data, output to the syndrome circuit, input/output of error position data and output of corrected data must be performed by time division. In particular, when decoding is repeated a plurality of times as with product codes, a buffer memory having high speed access must be used.
To ensure reliability of the memory, 1 bit error correction and 2 bit error detection are often used, a typical example being the (72, 64) binary linear code. Herein, xe2x80x9c72xe2x80x9d is the bit coding length and xe2x80x9c64xe2x80x9d is the bit information length, i.e. there are 8 check bits.
In such a decoding circuit, all coded bit data is often decoded in parallel, and there is often another circuit to detect errors. This type of code is described for example in xe2x80x9cFault Tolerance Systemsxe2x80x9d (Edited by the Institute of Electronics Information Communications of Japan (Denshi Joho Tsushin Gakkai) by Yoshihiro Toma, first edition published on Jun. 10, 1990).
FIG. 19 is a block diagram of a conventional decoding circuit for (72, 64) binary linear codes. In the figure, 66 is an 8 bit input OR circuit to which signals from the syndrome circuit 60 are input, 67 is a 72 bit input NOR circuit to which signals from the error position/magnitude detecting circuit 63 are input, 68 is a 2 bit AND circuit to which the outputs of the 8 bit input OR circuit 66 and 72 bit input NOR circuit are supplied, and 49 is a correction impossibility detection flag output terminal for outputting a correction impossibility detection flag from the 2 input AND circuit 68.
In the aforesaid construction when memory error correction is performed, as the data path has a parallel construction, 72 bit coded data is first input to the syndrome circuit 60. In the syndrome circuit 60, an 8 bit syndrome is generated from received data and output. The error position/magnitude detecting circuit 63 checks whether or not an 8 bit pattern of bit positions comprising a check bit determined by a parity check matrix is identical with the syndrome. The result is sent to the 72 bit input NOR circuit 67 and correction circuit 63, and at that time, 64 bits of an information part are sent to the correction circuit 64. The correction circuit 64 performs an XOR operation on the received information bits and the error detection result of each bit, and the result is output from the decoded data output terminal 65.
In this coding, error detection is performed on 2 bit errors. This means that if the syndrome is not xe2x80x9c0xe2x80x9d and it is not identical to the pattern of a parity check matrix of 72 bits coding length, correction is impossible and an error is detected. The 8 bit input OR circuit 66 checks that the 8 bits of the syndrome are not xe2x80x9c0xe2x80x9d, the 72 bit input NOR circuit 67 checks whether the error is not a 1 bit error, and the logical product of the two check results in the 2 bit AND circuit 68 is output from the correction impossibility detection flag output terminal 49.
The aforesaid construction and operation are also described for example in Japanese Patent Publication Sho 53-5099 (applied for by D. W. Price, Nov. 8, 1972).
Problems Which this Invention Attempts to Solve
As the conventional error correction coding/decoding method has the construction described hereinabove, it leaves a large number of problems as described hereinbelow.
The first problem is that if a 1 symbol, 10 bit Reed-Solomon code is used for 8 bit input/output data, an 8 bit/10 bit conversion circuit and a 10 bit/8 bit conversion circuit are necessary, symbol clocks must be generated both for 8 bits and 10 bits, and a bit clock is required.
The second problem is that a special circuit is required to check whether data is all xe2x80x9c1xe2x80x9d to verify erasure of a flash memory.
The third problem is that even when a slip occurs in an Reed-Solomon code in symbol units, correction decoding may leave the slip unchanged since the Reed-Solomon code is cyclic.
The fourth problem is that when coded data is stored in a memory, since input of received data, input/output to the decoding circuit and output of the decoded result are performed on a time division basis, a high speed access memory is required in order to perform a plurality of decoding operations. The fifth problem is that, to output an error correction impossibility flag in a (72, 64) binary linear code used for memory error correction, it is necessary to perform a 1 bit error check in 72 bits, and this requires a circuit to perform a logical computation on the result. This makes a long delay time inevitable, and requires a circuit with a large number of gates to perform the computation.
This invention was conceived to overcome the aforesaid problems inherent in the prior art. It aims to provide an error correction method and circuit which performs error correction, coding and decoding by means of a simple structure with very high reliability by handling only 8 bit symbols and eliminating redundant circuits.
Means Used to Overcome the Above Problems
In order to achieve the aforesaid objectives, this invention provides, as the error correction coding/decoding method, a method of coding/decoding Reed-Solomon codes formed of larger symbols than information data symbols, comprising a process wherein dummy data is set in the symbols of the Reed-Solomon codes exceeding the bit length of the information symbols and this dummy data is not transmitted, an adding process wherein, during decoding, dummy data is first added to the symbols of an information part as bit data which is insufficient to be a symbol of a Reed-Solomon code, a transmitting process wherein, when a check symbol is transmitted, parts corresponding to the bit lengths of information symbols are transmitted without modification, and parts exceeding the bit lengths of information symbols are transmitted together in bit lengths equivalent to the bit lengths of the information symbols after the parts corresponding to the bit lengths of information symbols are transmitted, a process wherein, when decoding is performed, dummy bits are added and a syndrome calculation is performed without modification on check symbol parts corresponding to the bit lengths of information symbols transmitted first, a syndrome calculation based on check bit data being performed on data transmitted together in parts exceeding the bit lengths of information symbols transmitted later, and a process which performs a Galois field summation on a syndrome based on information obtained first and check symbols.
In order to achieve the aforesaid objectives, this invention provides the error correction coding/decoding method comprising a process wherein, when performing coding and decoding of error correction codes, a 0/1 inversion is performed on all information and check bytes before transmission, and a 0/1 inversion is performed on the read data before decoding.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding method for coding and decoding of error correction codes whereof the coding length has been compressed, this method comprising a process for adding a data pattern to the compressed part to generate check symbols so that data in the information and check symbols which are all xe2x80x9c1xe2x80x9d become codes, then transmitting only information and check symbols, and on the decoding side, a process for adding syndrome data corresponding to data in the compressed part to a syndrome generated by the information and check symbols.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding method for coding and decoding of error correction codes whereof the coding length has been compressed, this method comprising a process for adding a code data pattern to a compressed part of an immediately preceding information symbol so as to generate a check symbol, then transmitting only information and the check symbol, and on the decoding side, a process for adding a syndrome corresponding to the code data pattern added to the compressed part, to a syndrome generated by the information and check symbol.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding circuit which stores received error correction coded data from a data input part in a buffer memory and performs a plurality of decoding operations according to the error correction code, this circuit comprising syndrome calculating means which perform a syndrome calculation on input data and on the data in the buffer memory, and means which perform decoding by selecting either one of these two syndromes and correcting errors.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding method wherein error correction coding and decoding comprises a process which treats the weighting of a parity check matrix only as xe2x80x9c1xe2x80x9d, xe2x80x9c3xe2x80x9d or xe2x80x9c7xe2x80x9d in a (76, 64) binary linear code that performs 1 bit error correction and 2 bit error detection.
In the error correction coding/decoding method, when 8 bits of information are processed as one symbol and a Reed-Solomon code is formed of larger symbols, dummy bits are added to insufficient bits so as to make one symbol. Eight bits of the Reed-Solomon check symbol thus formed are transmitted after the information symbol in the same way as information, while the surplus bits of the check symbol are transmitted together later. In decoding, dummy bits are added to the 8 bit information symbols and 8 bit check symbols, a syndrome calculation is performed, and a correction calculation is applied to the bit data in the check symbols grouping the surplus bits which are transmitted later.
In the error correction coding/decoding method, all information and check symbols are inverted before recording on a flash memory. When this data is read, by inverting and decoding, the all xe2x80x9c1xe2x80x9d of the erasure state of the flash memory can be processed as all xe2x80x9c0xe2x80x9d of coded data.
In the error correction coding/decoding method, dummy information is set in the compressed part to form a code even when the information and check bytes are all xe2x80x9c1xe2x80x9d. On the decoding side, syndrome data corresponding to data in the compressed part is added to the syndrome generated by information and check symbols.
In the error correction coding/decoding method, code data is assigned to the head of the compressed part. In coding, a check symbol is generated based on this coded data, and only information and check symbols are transmitted. In decoding, a syndrome corresponding to this code data pattern is added to the syndrome generated by this information and check symbols.
In the error correction coding/decoding circuit, either the syndrome corresponding to input data or syndrome corresponding to buffer memory data are selected, and error correction and decoding are performed based on this selection. This allows a reduced frequency of access to the buffer memory, and a lower operating speed of the buffer memory.
In the error correction coding/decoding method, during error coding and decoding, the weighting of the parity check matrix is arranged to be xe2x80x9c1xe2x80x9d, xe2x80x9c3xe2x80x9d, xe2x80x9c7xe2x80x9d in a (76, 64) binary linear code which performs 1 bit error correction and 2 bit error detection. In order to detect whether error correction is impossible, the weighting of the syndrome is found, and the detection is performed based on this weighting.